package com.mj.Heap;

import com.mj.printer.BinaryTreeInfo;
import com.mj.printer.BinaryTrees;
import com.sun.org.apache.xerces.internal.dom.PSVIAttrNSImpl;

import java.util.Comparator;

/**
 * @Author: LDeng
 * @Date: 2021-03-17 17:22
 */
public class Main {

    static void test1() {
        BinaryHeap<Integer> heap = new BinaryHeap<>();
        heap.add(68);
        heap.add(72);
        heap.add(43);
        heap.add(50);
        heap.add(38);
        heap.add(10);
        heap.add(90);
        heap.add(65);

        BinaryTrees.print(heap);
        System.out.println("\n");
        //heap.remove();
        System.out.println(heap.replace(70));
        BinaryTrees.print(heap);

    }

    static void test2() {
        Integer[] data = {74, 85, 7, 86, 91, 21, 73, 2, 1, 80, 83, 30, 5, 68};

        BinaryHeap<Integer> heap = new BinaryHeap<>(data);
//        for (int i = 0; i < data.length; i++) {
//            heap.add(data[i]);
//        }
        BinaryTrees.print(heap);


        BinaryHeap<Integer> heap2 = new BinaryHeap<>();
        for (int i = 0; i < data.length; i++) {
            heap2.add(data[i]);
        }
        BinaryTrees.print(heap2);
    }

    static void test3(){
        Integer[] data = {39, 65, 84, 12, 86, 17, 93, 82, 71, 67, 18, 31,
                55, 25, 47, 34, 95, 37, 96, 91, 40, 58, 80, 21, 69, 36};
        BinaryHeap<Integer> heap = new BinaryHeap<>(data,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });


        BinaryTrees.print(heap);

    }

    //求n个数中最大的前k个数
    static void test4(){
        Integer[] data = {39, 65, 84, 12, 86, 17, 93, 82, 71, 67, 18, 31,
                55, 25, 47, 34, 95, 37, 96, 91, 40, 58, 80, 21, 69, 36};
        //新建小顶堆
        BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        //最大前5个
        int k = 5;
        for (int i = 0; i < data.length; i++) {
            if (heap.size() < k) {
                //先装进去前5个遍历到的元素
                heap.add(data[i]);//logk
            } else if (data[i] > heap.get()) {//k+1个数开始
                //从第k+1个数开始，如果大于堆顶元素， 就是用replace 操作
                //即将第k+1个元素添加到堆中
                //大于堆顶元素，
                heap.replace(data[i]);//logk
            }
        }
        //O(nlogk)
        BinaryTrees.print(heap);
    }




    public static void main(String[] args) {


        test4();
    }
}
